arrays = [
    [9, 5, 3, 1, 2, 4, 6, 8, 7],
    [78, 56, 69, 22, 90, 66, 32, 56, 11, 29, 75, 33, 39, 65, 48, 61, 99, 84, 59, 17],
]


def partition(num, low, high):
    pivot = num[low]
    i, j = low, high
    while i < j:
        # 从右往左找比基准小的数
        while i < j and num[j] >= pivot:
            j -= 1
        # 从左往右找比基准大的数
        while i < j and num[i] <= pivot:
            i += 1

        if i < j:
            # 交换 左小数 和 右大数
            num[i], num[j] = num[j], num[i]

    print("-->", array)
    print(f"基准值{pivot}, {num[low+1:i]} -- {num[i:high]}")

    # 将基准数放到中间
    num[low], num[i] = num[i], num[low]

    return i


def quickSort(num, low, high):
    if low < high:
        i = partition(num, low, high)
        quickSort(num, low, i - 1)
        quickSort(num, i + 1, high)
    return num


def quick_sort(num):
    return quickSort(num, 0, len(num) - 1)


for array in arrays:
    print("排序结果", quick_sort(array))
